package lru

import "container/list"

// 基于lru的缓存实现


// 缓存
type Cache struct {
	// 内存上限大小
	maxBytes int64
	// 当前已经使用大小
	currentBytes int64
	// 双向链表
	ll *list.List
	// 用于缓存的map, key为字符串, value为链表元素
	cache map[string]*list.Element
	// callback, 当元素被移除时会回调该方法
	OnEvicted func(key string, value Value)
}


// 链表元素
type entry struct {
	key   string
	value Value
}


// 自定义的Value类型, 定义了Len的接口
type Value interface {
	Len() int
}


// 实例化Cache
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes: maxBytes,
		currentBytes: 0,
		ll: list.New(),
		cache: make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}


// 获取
/*
1. 获取对应key的Value
2. 如果Value存在则将其移到链表首部, 并返回Value的值
*/
func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok:= c.cache[key]; ok {
		//将其移到链表首部
		c.ll.MoveToFront(ele)
		// 类型转换
		kv := ele.Value.(*entry)
		return kv.value, true
	}

	return nil, false
}


// 删除旧的item
/*
1. 删除链表尾部的元素
2. 将该元素从map中移除
3. 更新当前所占用的空间大小
4. 回调通知有元素被删除了
*/
func (c *Cache) RemoveOldItem () {
	// 从尾部获取一个元素
	ele := c.ll.Back()
	if ele != nil {
		// 将元素从链表中移除
		c.ll.Remove(ele)
		// 将该元素从map中移除
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)
		// 更新当前所占用的空间大小
		c.currentBytes -= int64(len(kv.key)) + int64(kv.value.Len())
		// 回调通知元素被删除了
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)
		}
	}
}


// 增加/修改
/*
a. 新增的key是否已存在
	存在:
		1. 将该元素移到链表首部
		2. 更新当前占用的空间大小, 当前key对应的value大小可能会不同
		3. 更新value
	不存在:
		1. 添加元素到链表首部
		2. 更新当前占用的空间大小
		3. 将其加入到缓存
b. lru检测
*/
func (c *Cache) Add (key string, value Value) {
	if ele, ok := c.cache[key]; ok {
		// 将该元素移到链表首部
		c.ll.MoveToFront(ele)
		// 更新当前占用的空间大小, 当前key对应的value大小可能会不同
		kv := ele.Value.(*entry)
		c.currentBytes += int64(kv.value.Len()) - int64(value.Len())
		// 更新value
		kv.value = value
	} else {
		// 添加元素到链表首部
		ele := c.ll.PushFront(&entry{key: key, value: value})
		// 更新当前占用的空间大小
		c.currentBytes += int64(len(key)) + int64(value.Len())
		// 将其加入到缓存
		c.cache[key] = ele
	}

	// lru检测
	if c.maxBytes > 0 && c.currentBytes >= c.maxBytes {
		c.RemoveOldItem()
	}
}


// 返回当前缓存中元素的总个数
func (c *Cache) Len() int {
	return c.ll.Len()
}

